package com.gitee.feizns.explore.data_structure.array.easy;

import java.util.HashSet;
import java.util.Set;

/**
 * 219. 存在重复元素 II
 * @author feizns
 * @since 2020/1/9
 */
public class ContainsNearbyDuplicate {

    public static void main(String[] args) {
        System.out.println(containsNearbyDuplicate2(new int[]{1, 2, 3, 1}, 3));
    }

    public static boolean containsNearbyDuplicate(int[] num, int k) {
        for (int i = 0; i < num.length; i++) {
            for (int j = i + 1; j <= i + k && j < num.length; j++) {
                if ( num[i] == num[j] )
                    return true;
            }
        }
        return false;
    }

    public static boolean containsNearbyDuplicate2(int[] num, int k) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < num.length; i++) {
            if ( set.contains(num[i]) )
                return true;
            set.add(num[i]);
            if ( i - k >= 0 )
                set.remove(num[i - k]);
        }
        return false;
    }

}
